package 中等.动态规划.子序列;

/**
 * 给你一个整数数组 nums 和一个 正 整数 k 。
 * nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：
 * (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k
 * 返回 nums 的 最长有效子序列 的长度。
 *
 * @ https://leetcode.cn/problems/find-the-maximum-length-of-valid-subsequence-ii/description/?envType=daily-question&envId=2025-07-17
 * @date 2025/07/26
 */
public class 找出有效子序列的最大长度II_3202 {

    public static void main(String[] args) {

    }

    /**
     * 枚举 (sub[1] + sub[2]) % k 的值 [0,k-1]
     * 1，先将每个元素 %k 答案不会有影响
     * 2，假设求(sub[1] + sub[2]) % k = m = 1，可能的序列有 10101... 0101...
     * 3，确定了当前元素为 1，那么前面的元素必须是 m-1
     * 4，定义dp[i]表示，遍历到i元素时，i元素结尾的子数组最大长度是多少
     * dp[i] = dp[(m-i+k)%k]+1
     */
    public int maximumLength(int[] nums, int k) {
        int ans = 0;
        for (int m = 0; m < k; m++) {
            int[] dp = new int[k];

            for (int i : nums) {
                i %= k;
                dp[i] = dp[(m - i + k) % k] + 1;
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }

}
